1. Field of the Invention
The present invention generally relates to computer networks. More particularly, the invention relates to electronic switches through which communications pass from one point in a network to another. Still more particularly, the invention relates to an improved technique for synchronizing topology databases between switches in a network.
2. Background Information
Initially, computers were most typically used in a standalone manner. It is now commonplace for computers and other types of computer-related and electronic devices to communicate with each other over a network. The ability for computers to communicate with one another has lead to the creation of networks ranging from small networks comprising two or three computers to vast networks comprising hundreds or even thousands of computers. Networks can be set up to provide a wide assortment of capabilities. For example, networks of computers may permit each computer to share a centralized mass storage device or printer. Further, networks enable electronic mail and numerous other types of services. Generally, a network's infrastructure generally comprises switches, routers, hubs and the like to coordinate the effective and efficient transfer of data and commands from one point on the network to another.
Networks often comprise a “fabric” of interconnected switches which are devices that route data packets from a source port to a destination port. FIG. 1 shows an exemplary switch fabric comprising switches 20, 22, 24, 26 and 28. Various devices including servers, storage devices, etc. connect to some or all of the switches. In FIG. 1, devices D1 and D2 connect to switch 20 and device D3 connects to switch 24. Through the fabric of switches, devices D1-D3 can communicate with each other by sending and receiving data frames. The switch fabric takes care of routing the data frames from the source to their intended destination.
The switches shown in FIG. 1 are interconnected by communication links typically referred to as inter-switch links (“ISLs”). As shown, switches 22 and 24 are connected by a single ISL 17, as are switches 24 and 26, switches 26 and 28, and switches 20 and 28. Switch 20 connects to switch 22 by four ISLs (identified collectively by numeral 19), as also is the case with switches 20 and 26. Multiple ISLs between a pair of switches increases the effective bandwidth between the switches and provides redundancy in the case of a link failure.
Each switch generates and maintains a link state record (“LSR”). The LSRs for switches 20-28 are shown as LSRs 21-29, respectively in FIG. 1. The LSRs are stored in memory 15 which is coupled to and accessible by a CPU 13 in each switch. Each LSR for a switch specifies how that switch is connected to its neighboring switches. Two switches connected directly via an ISL are referred to as “neighbors.” For example, the neighbors of switch 20 are switches 22, 26 and 28, but not switch 24 because switch 24 does not connect via an ISL directly to switch 20. Switch 20 can communicate with switch 24 via either switch 22 or switch 26.
Each switch includes multiple ports and the ISLs are formed between ports of neighboring switches. Not all of a switch's ports need be used at any point in time. The switches in FIG. 1 may be, for example, 16 port switches. Switch 20 is shown as having nine ports (numbered 1-9) connected via ISLs to neighboring switches 22, 26 and 28, while switches 22 and 26 only use five and six, respectively, of their ports to connect to their neighbors.
As mentioned above, each switch's LSR specifies how the switch connects to its neighbors. The connectivity information in an LSR includes the switch's “domain identifier,” and for each neighboring (i.e., remote) switch, the remote switch's domain identifier, remote port number and local port number. For example, as shown, port 1 of switch 20 connects to port 7 of switch 22. For purposes of this disclosure, the domain identifiers of each switch will be the reference numerals shown in the various figures. Thus, “20” is the domain identifier for switch 20, “22” is the domain identifier for switch 22, and so on. The connectivity information contained in the LSR 21 associated with switch 20 that describes the ISL between ports 1 and 7 of switches 20 and 22 will include remote domain identifier “22,” local port number “1,” and remote port number “7.” This type of information is included in LSR 21 for each ISL between connecting switch 20 to a neighbor switch.
FIG. 2 shows an LSR 21 for switch 20. Each entry in the LSR pertains to a separate ISL and other information (e.g., age, incarnation number, etc.) may be included on the LSR. Because there are four ISLs to switch 22, four ISLs to switch 26 and one ISL to switch 28, the LSR 21 shown in FIG. 2 includes four entries pertaining to neighboring switch 22, four entries pertaining to neighboring switch 26 and one entry pertaining to neighboring switch 28. Each entry identifies the local and remote ports forming that ISL.
The last column in the LSR of FIG. 2 is labeled as “cost.” Each ISL in the network is assigned a cost value that is arbitrary in magnitude, but inversely related to the bandwidth of the ISL. For example, a 1 gigabit per second (“gbps”) link may be assigned a cost value of 1000, while a 2 gpbs link may be assigned a cost value one-half as much (i.e., 500). As such, lower costs indicate faster links. The switches in the network preferably determine a priori the lowest cost path between end points on the network by adding together the costs of the various links forming each possible path through the fabric and determining which path or paths has the lowest total cost. The lowest cost path is selected to be the path through which traffic is routed between end points. For example, there are three possible paths for traffic to take from device D1 to device D3 in FIG. 1. The three paths include switches 20-22-24, 20-26-24, and 20-28-26-24. Whichever path has the lowest total cost is the path assigned for traffic to be routed from device D1 to device D3. In FIG. 2, the cost values are all set at 1000, but in general the cost values can be different between the various entries in the LSR and be changed as desired.
For data frames to be routed accurately and efficiently through the fabric, each switch must be aware of the network's topology, that is, how all of the switches are connected together. Each switch initially only knows its connectivity information in its own LSR, and not the LSR information pertaining to the other switches in the fabric. Through a standardized synchronization process (described below), the switches exchange LSR information and propagate such information to other switches in the fabric. The collection of LSRs associated with two or more switches is referred to herein as the “topology database.” The switches exchange their topology databases so that each switch can be made aware of how other switches in the network are connected together.
FIG. 3 depicts the standardized process for synchronizing the topology databases of the switches in the fabric. The process begins in step 30 when an ISL forms between a pair of switches. Each switch detects when a physical connection is made to a neighboring switch. In step 32, once a local switch detects one of its ports is connected to a neighboring switch, the local switch begins a “HELLO” protocol in which the switch sends HELLO messages to the neighboring switch. The HELLO message essentially announces the local switch's presence to the neighboring switch and includes connectivity information for use by the neighboring switch. Such connectivity information includes the local switch's domain, the local switch's port number used for the new ISL and, if known, the remote (i.e., neighboring) switch's domain and port number. These values are included in various fields in the HELLO message. At first, the local switch will not know the remote switch's domain and port number and thus fills those fields in with predetermined values such as all “F” hexadecimal values. The remote switch, once it detects the new connection also begins sending HELLO messages including the its domain and port numbers, leaving the other switch's domain and port numbers as all F's. Thus, as indicated in step 34, both switches provide each other their domain and port number.
Once the switches are informed of the neighbor's domain and port number, in step 36 the switches exchange their topology databases which includes the LSRs describing all of the ISLs each switch knows about. These databases may require more than one message frame to complete the transfer. Thus, in step 38 once a switch has sent all of its topology database to its new neighbor, the switch sends a final frame that is precoded to indicate to the neighbor that the neighbor has received all of the topology database. The neighbor generally will not proceed to the next state in its state machine until it receives this precoded end of database exchange sequence frame. Once the end of the database exchange sequence frame is received, the neighbor responds back with an acknowledgment frame indicating that it has received the entire topology database. In step 40 each switch then transitions the state of the new ISL to the FULL state to permit the ISL to be used for normal network traffic. Finally, each switch updates its own LSR to include the connectivity information regarding the newly established ISL and propagates the updated LSR via all other of its ports to all other neighboring switches.
Each port on a switch performs the process outlined above when physical connection from that port to a neighboring switch is detected. Because the state machine for each port is the same, the design of the switch is relatively straightforward. However, the database synchronization process described above is inherently inefficient because the same topology database is copied over each and every link between the same pair of switches. The database synchronization process works well when each switch has relatively few ports, but the inherent inefficiency becomes more troublesome as network switch technology progresses and the number of ports on each switch increases. Today's switches typically have 16 ports and 64 port switches are becoming available. Thus, although the current topology database synchronization process generally works well, like most technology, improvements are always welcome. Moreover, an improved topology database synchronization process is needed which avoids or mitigates the inefficiency described above.
When there is a change in the state of an ISL (addition of removal), the change is reflected in the LSR of the switches (addition or removal of an entry) that detects the change. For each change in the LSR of a switch, the switch needs to update its LSR and transmit the new LSR on all other ISLs. This is also inefficient and becomes troublesome as networks become larger and the port count on the switches increase. Today's switches typically have 16 ports and 64 port switches are becoming available. Thus, although the current LSR update process generally works well, like most technology, improvements are always welcome. Moreover, an improved LSR update process is needed which avoids or mitigates the inefficiencies described above.